Phát biểu Bổ đề Johnson–Lindenstrauss

Với mọi 0 < ε < 1, tập hợp X gồm m điểm trong RN, và một số nguyên n > n 0 = O(ln(m) / ε 2), tồn tại một hàm Lipschitz ƒ : RN → Rn sao cho

( 1 − ε ) ‖ u − v ‖ 2 ≤ ‖ f ( u ) − f ( v ) ‖ 2 ≤ ( 1 + ε ) ‖ u − v ‖ 2 {\displaystyle (1-\varepsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|u-v\|^{2}}

với mọi u, v ∈ X.

Một cách chứng minh bổ đề là chọn ƒ là phép chiếu xuống một không gian ngẫu nhiên n chiều trong RN, và sử dụng hiện tượng tập trung độ đo.

Số chiều của bổ đề là chặt cho tới thừa số log(1/ε), nghĩa là tồn tại m điểm sao cho để giữ nguyên khoảng cách giữa các điểm tới thừa số 1+ε, cần sử dụng

Ω ( log ⁡ ( m ) ε 2 log ⁡ ( 1 / ε ) ) {\displaystyle \Omega \left({\frac {\log(m)}{\varepsilon ^{2}\log(1/\varepsilon )}}\right)}

chiều.[1]

Liên quan